package main

import (
	"fmt"
	"math/rand"
	"time"
)

//冒泡排序耗时= 3611730300 纳秒
//选择排序耗时= 1080395400 纳秒
//插入排序耗时= 415756200 纳秒
//快速排序耗时= 4381200 纳秒

func main() {
	var num = 10000 * 5
	slice := GenSlice(num)
	var slice1 []int = make([]int, num)
	copy(slice1, *slice)
	BubbleSortMinToMaxSlice(&slice1)

	var slice2 []int = make([]int, num)
	copy(slice2, *slice)
	selectSortMinToMax(&slice2)

	var slice3 []int = make([]int, num)
	copy(slice3, *slice)
	insertSortMinToMax(&slice3)

	var slice4 []int = make([]int, num)
	copy(slice4, *slice)
	nano := time.Now().UnixNano()
	QuickSortMinToMax(0, len(slice4)-1, &slice4)
	fmt.Println("快速排序耗时=", time.Now().UnixNano()-nano, "纳秒")
}

func GenSlice(n int) *[]int {
	var arr []int = make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(10 * 10000)
	}
	return &arr
}

// BubbleSortMinToMaxSlice
//
//	@Description: 冒泡排序
func BubbleSortMinToMaxSlice(arr *[]int) {
	nano := time.Now().UnixNano()
	var maxTemp = 0
	//排序次数
	for times := 0; times < len(*arr)-1; times++ {
		//从第一个开始，将最大的放到最后
		for i := 0; i < len(*arr)-1-times; i++ {
			//如果前面的比后面大，则交换
			if (*arr)[i] > (*arr)[i+1] {
				maxTemp = (*arr)[i+1]
				(*arr)[i+1] = (*arr)[i]
				(*arr)[i] = maxTemp
			}
		}
	}
	fmt.Println("冒泡排序耗时=", time.Now().UnixNano()-nano, "纳秒")
}

// insertSortMinToMax
//
//	@Description: 插入排序法
//	@param arr
func insertSortMinToMax(arr *[]int) {
	nano := time.Now().UnixNano()
	for i := 1; i < len(*arr); i++ {
		//第一次，给第二个元素找位置，第二次，给第三个元素找位置，依次类推
		insertValue := (*arr)[i]
		beforeIndex := i - 1 //下标

		for beforeIndex >= 0 && (*arr)[beforeIndex] > insertValue { // 前面的小于后面的
			(*arr)[beforeIndex+1] = (*arr)[beforeIndex] //数据后移
			beforeIndex--                               //索引前移
		}

		//插入
		(*arr)[beforeIndex+1] = insertValue
	}
	fmt.Println("插入排序耗时=", time.Now().UnixNano()-nano, "纳秒")
}

// QuickSortMinToMax 快速排序
func QuickSortMinToMax(left int, right int, array *[]int) {

	if left >= right {
		return
	}

	l := left
	r := right
	pivot := (*array)[(left+right)/2]

	// 目标：将比 pivot 小的元素放在左边，比 pivot 大的元素放在右边
	for l <= r {
		// 从左边开始找比 pivot 大的元素
		for l <= r && (*array)[l] < pivot {
			l++
		}
		// 从右边开始找比 pivot 小的元素
		for l <= r && (*array)[r] > pivot {
			r--
		}
		// 本次循环结束
		if l <= r {
			// 交换
			(*array)[l], (*array)[r] = (*array)[r], (*array)[l]
			l++
			r--
		}
	}

	// 向左递归
	if left < r {
		QuickSortMinToMax(left, r, array)
	}
	// 向右递归
	if l < right {
		QuickSortMinToMax(l, right, array)
	}

}

// @return error  选择排序
func selectSortMinToMax(arr *[]int) {
	nano := time.Now().UnixNano()
	for i := 0; i < len(*arr); i++ {
		minIndex := getMinIndex(arr, i)
		if (*arr)[minIndex] < (*arr)[i] {
			(*arr)[minIndex], (*arr)[i] = (*arr)[i], (*arr)[minIndex] // 交换 golang特有写法
		}
	}
	fmt.Println("选择排序耗时=", time.Now().UnixNano()-nano, "纳秒")
}

// getMinIndex 找到从 start 开始的最小元素的下标
//
// @param arr 指向固定大小为10的整数数组的指针
// @param start 开始查找的起始索引
// @return int 最小元素的下标
func getMinIndex(arr *[]int, start int) int {
	minIndex := start
	for i := start + 1; i < len(*arr); i++ {
		if (*arr)[i] < (*arr)[minIndex] {
			minIndex = i
		}
	}
	return minIndex
}
